package Algorithm.SlidingWindow;
//https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/submissions/
//689. 三个无重叠子数组的最大和
public class Leetcode689_notice_maximum_sumof_3_non_overlapping_subarrays {
    //如果维持这三个下标是一个难点
    class Solution {
        public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
            int i1 = 0;
            int j1 = i1 + k - 1;
            int i2 = j1 + 1;
            int j2 = i2 + k - 1;
            int i3 = j2 + 1;
            int j3 = i3 + k - 1;

            int[] result = new int[3];
            result[0] = i1;
            result[1] = i2;
            result[2] = i3;

            int sum1 = 0;
            int sum2 = 0;
            int sum3 = 0;

            for(int n=0;n<k;n++){
                sum1 += nums[i1+n];
                sum2 += nums[i2+n];
                sum3 += nums[i3+n];
            }

            int max1 = sum1;
            int max2 = max1 + sum2;
            int max3 = max2 + sum3;
            int maxIndex = i1;
            int maxIndex12 = i1;
            int maxIndex2 = i2;

            for(int n = j3;n<nums.length-1;n++){
                j1++;
                sum1 = sum1 - nums[i1] + nums[j1];
                i1++;
                if(sum1 > max1){
                    max1 = sum1;
                    maxIndex = i1;
                }

                j2++;
                sum2 = sum2 - nums[i2] + nums[j2];
                i2++;
                if((max1 + sum2) > max2){
                    max2 = max1 + sum2;
                    maxIndex12 = maxIndex;
                    maxIndex2 = i2;
                }

                j3++;
                sum3 = sum3 - nums[i3] + nums[j3];
                i3++;
                if((max2 + sum3) > max3){
                    max3 = max2 + sum3;
                    result[0] = maxIndex12;
                    result[1] = maxIndex2;
                    result[2] = i3;
                }
            }

            return result;

        }
    }
}
